[CS50]2019哈佛大學程式課程Week2

發表於 更新於 分類於

這篇是 week2, 開頭先分享資源和系列文章連結:

系列文章:

執行寫有程式碼的檔案到底發生了什麼事情

大概是說我們知道 clang 可以 compile .c file 然後可以執行它, 過程中就是把我們的 code 編譯成電腦懂的 binery 語言, 已經抽象到統稱他為 compile, 但其實程序做了不少事情, 以下為四個步驟:

  • preprocessing
  • compiling
  • assembling
  • linking

preprocessing

電腦基本上只懂得 binery 的語言, 就是一堆 010101 的東西, 所以需要有 compiler 這個過程翻譯

課程上介紹最基本的範例是用 clang 去 compile 一個 C 語言的檔案, 即可執行它, 例如:
$ clang -o hello hello.c #=> same as $ make hello
然後就可以執行 compile 出來的檔案
$ ./hello

現在檔案只要在開頭

1
2
#include <cs50.h>
#include <stdio.h>

compile 後就可以在裡面寫上 get_string 的方法, 可以注意到執行指令上會有一段 -lcs50, 其中 l 代表 libery, 這代表加上了 cs50 這個套件(libery)的程式碼, 實際上發生的事情是引入了許多 cs50 binery 的程式碼

compiling

clang 會把 .c file 先編譯成 assembly language, 基本上人類已經看不太懂, 是給 CUP 看的

assembling

會把 assembly language 在轉換成完全的電腦語言 binery

linking

剛剛在 preprocessing 步驟有提到 .c file 裡面開頭貼上 #include <cs50.h> 引入了許多 cs50 binery 的程式碼, 到這裡會把所有的 binery 程式碼連結成一塊, 所以對我們來說真正有了 get_string 可以直接 coding

電腦如何運算

電腦有個硬件叫 CPU 可以專做運算

籠統地來說可以先可以想像 CPU 裡面有三種空間, 且空間內有很多儲存格
空間1 -> 寫入固定的東西在裡面
空間2 -> 先空著準備拿來做運算
空間3 -> 專門做運算

假設今天要計算 33 等於多少
3 3 = 3 + 3 + 3
3 是放在空間1某個儲存格的值, 正常是個 binery, 電腦已經幫我們翻譯成 3 這個數字

step1. 空間2會挪出一個儲存格先放空間1的 3
step2. 再拿一個空間3先算出第一個 3 + 3 放回剛剛空間2的那一個儲存格
step3. 重複第二個步驟現在空間2的那一個儲存格就是我們要的答案

你可以想像我們人腦背 9 * 9 是離所當然的事情, 為什麼電腦這麼笨要計算這麼多次這麼久
但其實以現在的 CPU 來說一秒可以執行幾億個 step, 他要計算 3.14^10 也不過是一瞬間的事情了

最後這個例子只是想用白話解釋一下, 真正運作可能不是這樣子的

Array

Array 可以把他視為陣列的變數, 如剛剛說的儲存格, 譬如說一個字串 ‘Kurt’ 可以把他想像成有四個儲存格組成 ‘Kurt’ 這個字串, 而讀取每一個字串的方法如下(我用 ruby 示範):

1
2
3
4
5
str = 'Kurt'
puts str[0] # => 'K'
puts str[1] # => 'u'
puts str[2] # => 'r'
puts str[3] # => 't'

如何有計算字串的長度可以使用

如同第一個主題所說引入別人的 libery(例如 cs50.h) 之後就有些 method 可以使用, 加上剛剛 Array 的特性, 影片用 C 語言做一個示範:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(viod)
{
  string s = get_sting("Name: ");

  int n = 0;
  # '\0' 代表字串結束
  while(s[n] != '\0')
  {
    n++
  }

  pringf('The length of your name is %i\n, n')
}

所以這個檔案可以計算字串長度了!

C 語言本身是沒有計算長度的方法的, 只是有人像上面範例一樣做出一些方法, 並且整理得更好, 然後在別的檔案 include 進來就可以使用了

計算法

如果要排列一群數字有三種方法:

  1. 從頭到尾每兩個數字比對, 比較小的排前面 (最花時間)
  2. 每次找出最小的數字直接放到最前面 (還是蠻花時間)
  3. 每一次兩組比對, merge 後第二次再拿兩組比對, 每次比對最小的數字放前面 (花的時間指數下降)

第三種方法文字有點難解釋XD

總之可以想像當一個數字在做移動時就會消耗一個記憶體, 三個方法每一回合執行的時間如果都固定的話最後一個方法執行的回合最少之外移動的也是最少

這都是許多天才想出來讓我們電腦運算越來越快的一個例子

其他穿插的紀錄

有時候會突然講一些小東西, 我沒辦法連貫所以記錄下來

  1. 不論成功失敗永遠都要回傳東西, 成功或錯誤訊息 or boolean
  2. 雖然電腦計算很快, 但過多的 loop 或過少的變數設計在程式碼越多和越複雜的情況下效能還是會差異的可怕
  3. 加密的東西需要一把鑰匙另一頭人才可以解密, 現在電腦許多的協議以及工具已經可以做到安全性蠻高的